package com.meterhuang;

import lombok.extern.slf4j.Slf4j;

/**
 * 二叉树遍历:回溯法的经典案例
 *
 * @author meterhuang
 * @date 2021/04/07 10:18
 */
@Slf4j
public class TreeOrderTraversal {

	public static void main(String[] args) {
		TreeNode[] tree = new TreeNode[7];
		char ch = 'A';
		for (int i = 0; i < tree.length; i++) {
			tree[i] = new TreeNode(ch);
			ch++;
		}
		// 序号0,1,2....,9
		for (int i = 0; i < tree.length; i++) {
			if (i * 2 + 1 < tree.length) {
				tree[i].left = tree[2 * i + 1];
			}
			if (i * 2 + 2 < tree.length) {
				if (i == 2) {
					continue;
				}
				tree[i].right = tree[2 * i + 2];

			}
		}
		// 额外新增一个子节点
		tree[6] = new TreeNode('G');
		tree[3].left = tree[6];
		// 中序遍历: DBEAFC
		middleTraverse(tree[0]);
		// 前序遍历: ABDECF
		leftTraverse(tree[0]);
		// 后序遍历: DEBFCA
		rightTraverse(tree[0]);
	}

	private static void middleTraverse(TreeNode root) {
		if (root.left != null) {
			middleTraverse(root.left);
		}
		log.info("middle: {}", root.data);
		if (root.right != null) {
			middleTraverse(root.right);
		}
	}

	private static void leftTraverse(TreeNode root) {
		log.info("pre: {}", root.data);
		if (root.left != null) {
			leftTraverse(root.left);
		}
		if (root.right != null) {
			leftTraverse(root.right);
		}
	}

	private static void rightTraverse(TreeNode root) {
		if (root.left != null) {
			rightTraverse(root.left);
		}
		if (root.right != null) {
			rightTraverse(root.right);
		}
		log.info("post: {}", root.data);
	}

	/**
	 * 树节点对象
	 */
	static class TreeNode {
		private char data;
		private TreeNode left;
		private TreeNode right;
		public TreeNode(char data) {
			this.data = data;
		}

		@Override
		public String toString() {
			return String.valueOf(data);
		}
	}
}
